
import libnum
import gmpy2

n = 8308051515501311964334260730128014509750463265848748111625284717303627756997695324364598300546005434993341842804118425218860148239234883356713233473299417
c = 1629372979029027026955013757562248194762457696260155573160758898619237265168092458856424970011032509286652929845078754109827454943080817390725723969634550
e = 65537

q1,s=gmpy2.iroot(n,2)
q=gmpy2.next_prime(q1)
p=n//q
print(n==p*q)
b = p-1
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m1 = pow(c,d,n)
m = m1^(b**2)
print(libnum.n2s(int(m)))




